/**
 * @author VernHe
 * @date 2021年05月17日 17:44
 */
public class Solution_079 {
    public static void main(String[] args) {
//        char[][] board = new char[][]{
//                {'A','B','C','E'},
//                {'S','F','C','S'},
//                {'A','D','E','E'}
//        };
//        String word = "ABCCED";
//        char[][] board = new char[][]{
//                {'A','B','C','E'},
//                {'S','F','C','S'},
//                {'A','D','E','E'}
//        };
//        String word = "SEE";
        char[][] board = new char[][]{
                {'A','B'}
        };
        String word = "BA";

        System.out.println(new Solution_079().exist(board,word));
    }

    public boolean exist(char[][] board, String word) {
        // 参数判断
        if (board == null || board.length == 0 || board[0].length == 0 || word == null) {
            return false;
        }
        int wordLen = word.length();
        if (wordLen == 0) {
            return true;
        }
        // 行数
        int rows = board.length;
        // 列数
        int cols = board[0].length;
        char[] words = word.toCharArray();
        System.out.println("words的长度：" + words.length);
        // 二维数组，用于记录走过的路径
        byte[][] selected = new byte[rows][cols];

        // 找到首字母符合的
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] == words[0]) {
                    // 进行dfs查找，看是否匹配
                    selected[row][col] = 1;
                    if (dfs(row,col,selected,1,board, words)) {
                        return true;
                    }
                    // 能到这里说明发生了回溯
                    selected[row][col] = 0;
                }
            }
        }

        return false;
    }

    /**
     *  深度优先查找
     * @param row           当前row
     * @param col           当前col
     * @param selected      已经被选择过的
     * @param wordNum       已经选了几个字母
     * @param board         字符网格
     * @param words         要找的字符串的字符数组
     * @return
     */
    private boolean dfs(int row, int col, byte[][] selected, int wordNum, char[][] board, char[] words) {
        System.out.println("wordNum: " + wordNum + ", row: " + row + ", col: " + col);
        // 递归基
        // 如果找到了
        if (wordNum == words.length) {
            return true;
        }
        // dfs查找
        // 向上
        if (row - 1 >= 0 && selected[row - 1][col] == 0 && words[wordNum] == board[row - 1][col]) {
            selected[row - 1][col] = 1;
            if (dfs(row - 1, col, selected, wordNum + 1, board, words)) {
                return true;
            }
            // 到这里说明发生了回溯
            selected[row - 1][col] = 0;
        }
        // 向右
        if (col + 1 < board[0].length && selected[row][col + 1] == 0 && words[wordNum] == board[row][col + 1]) {
            selected[row][col + 1] = 1;
            if (dfs(row, col + 1, selected, wordNum + 1, board, words)) {
                return true;
            }
            // 到这里说明发生了回溯
            selected[row][col + 1] = 0;
        }
        // 向下
        if (row + 1 < board.length && selected[row + 1][col] == 0 && words[wordNum] == board[row + 1][col]) {
            selected[row + 1][col] = 1;
            if (dfs(row + 1, col, selected, wordNum + 1, board, words)) {
                return true;
            }
            // 到这里说明发生了回溯
            selected[row + 1][col] = 0;
        }
        // 向左
        if (col - 1 >= 0 && selected[row][col - 1] == 0 && words[wordNum] == board[row][col - 1]) {
            selected[row][col - 1] = 1;
            if (dfs(row, col - 1, selected, wordNum + 1, board, words)) {
                return true;
            }
            // 到这里说明发生了回溯
            selected[row][col - 1] = 0;
        }

//        A  B  C  E      A  B  C
//        S  F  C  S            C
//        A  D  E  E         D  E

        for (byte[] bytes : selected) {
            for (byte b : bytes) {
                System.out.printf(String.valueOf(b));
            }
            System.out.println();
        }
        System.out.println("--------------");
        // 到达这里说明都没找到
        return false;
    }
}
